1. Field of the Invention
The present invention relates to Medium Access Control (MAC) methods and apparatuses in a wireless distributed network, and more particularly to a distributed MAC method and apparatus for scheduling respective transmissions between respective independent transmission node pairs, to effectively reduce probability of packet collision occurring in accessing channels, and to improve throughput and decrease the system overhead caused by control packets.
2. Description of Prior Art
With the prevalence of the wireless portable terminals and the rapid development of the wireless communication service in various fields, the future mobile communication systems are required to implement an “ubiquitous” communication, that is to say, to ensure effective wireless transmission at anytime and anywhere.
In a conventional cellular network, the communications between the mobile terminals must be achieved by use of the handover of base stations and (or) mobile switches, which makes the communication limited by some factors such as geographical regions. Thus, a Wireless Local Area Network (WLAN) is proposed as a more flexible wireless access network in order to be the supplement and development to the fixed network, thereby making the “ubiquitous” communication possible. The WLAN generally has two different network structures, either using a wireless access point to achieve inter-terminal communications in the network such as Bluetooth and Distributed Antenna System (DAS), or using random resource competition in an ad hoc manner to achieve flexible networking such as a typical system with Mobile Ad Hoc Network (MANET). Since the former still uses a centralized control similar to that in a cellular network, in some environments such as an area not accessible by the signal from the central controller, the mobile communication technique cannot work. In the case of the latter, a wireless distributed network, which is completely distributed and doesn't rely on any infrastructures, will therefore be a more effective manner for extending network and achieving the “ubiquitous” communication.
For such wireless distributed networks without fixed equipments, a set of mobile terminals equipped with wireless transceiver will flexibly constitute a temporary multi-hop autonomous system with recognized protocols. Because there is no absolute central control unit in the network, all the nodes are equivalent, and the nodes in the network cooperate using distributed algorithms without manual intervention and any other preset network facilities. Therefore, quick deployment of the network at anytime and anywhere is achieved. However, independency of respective nodes in the wireless distributed network makes each node only able to use its own information to determine channel competitions, so the randomness of the resource sharing increases. Thus, it becomes an important factor affecting the overall performance of the wireless distributed network which distributed algorithm is used to coordinate the respective behaviors, that is, the medium access control method.
Medium access control is a protocol in which multiple users or nodes fairly and effectively share a channel. According to the presence or absence of a central control unit in the network, it may be classified into centralized and distributed medium access control methods. In the medium access control methods in which the coordination is performed by the central control unit, the control unit uniformly schedules the transmissions of each node based on its knowledge about requirements and communication conditions of all the nodes in the network, and thus can effectively utilize the resources. But, due to the existence of the central control unit (node), the system overhead inevitably increases, and the flexibility of the system is reduced. Therefore, in practical application, the distributed networks are mostly used, which facilitates the rapid self-organization of networks, and fully reflects the self-organization character of the wireless network. However, the independent resource competition of each node in the wireless distributed network will inevitably result in packet collision. As compared with the former, the distributed medium access control method is subjected to the following problem: a major object for designing a distributed medium access control method is how to reduce a probability of packet collision and improve throughput as much as possible on the basis of as little as possible knowledge about information of other nodes.
The earliest and the most basic distributed medium access control method is ALOHA protocol proposed by N. Abramson. See N. Abramson, The ALOHA system-Another alternative for computer communications, Proc. AFIPS Conf. Montvale, N.J.: AFIPS Press, 1970, vol. 37. This prior art proposes a scheme in which each node in the network immediately sends data on the channel once a packet arrives.
In order to decrease the probability of packet collisions, L. Kleinrock and S. Lam propose to slot the time axis, and require that a transmitting time instant of a user must be the beginning of a discrete slot, that is, S-ALOHA. See L. Kleinrock and S. Lam, Packet-switching in a Slotted Satellite Channel, Proc. Nat. Computer Conf., AFIPS Conf., vol. 43, 1973, pp. 703-701. However, such a random access protocol for packet collisions can only achieve a maximum channel utilization ratio of 36%, resulting a severe resource waste. For this reason, L. Kleinrock and F. A. Tobagi further propose a carrier sense protocol. See CSMA, L. Kleinrock and F. A. Tobagi, Packet Switching in Radio Channels: Part I—Carrier Sense Multiple Access Modes and their Throughput-delay Characteristics, IEEE Trans. Commun., vol. COM-23, pp. 1400-1416, December 1975, which discloses using the sensed channel conditions as a basis of packet transmissions, such that the packets are sent only when the sensed channel is in an idle state. Based on the principle of CSMA, Sidhu, R. Andrews and A. Oppenheimer propose a Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) protocol. See G. Sidhu, R. Andrews, A. Oppenheimer, Inside Appletalk, Addison-Wesley, 1989, in which the system performance is further improved by randomizing the channel access time instants. Due to the simple implementation, it is widely used. However, with the development of the communication networks, the wireless distributed network is required to support higher-speed data transmissions and more extensive services. These distributed medium access control protocol cannot fulfill the network requirements, especially in that problems of hidden terminals and exposed terminals become the barrier factors for the performance improvement.
The problem of hidden terminals means that two transmitting nodes outside respective sensing ranges with respect to each other send data packets to one and the same receiving node. At the receiving node, packets from two different transmitting nodes will collide, which results in the deterioration of the system performance. On the other hand, when two transmitting nodes can sense each other's transmissions and their respective receiving nodes are out of the respective sensing ranges, one node suppresses its own packet transmissions once it senses that the other node is sending. But in fact, a simultaneous packet transmission of these two pairs will not influence each other. Such a transmission may be performed but is forbidden due to the sensing of peripheral nodes' transmissions will waste the system resources, which is known as the problem of exposed terminals.
For solving the above problems, some medium access control methods propose to use some short control packet switching information before data packet transmissions in order to reduce the collision probability of data packets. In P. Karn's MACA method, see P. Karn, MACA: a New Channel Access Method for Packet Ratio, IEEE Computer Networks Conference, 1990, the carrier sense is no longer utilized. But it is proposed to exchange short Request To Send (RTS) packet and Clear To Send (CTS) packet in order to preserve channels for subsequent data packet (DATA) transmissions. V. Bharghavan et al proposed an MACAW method, see V. Bharghavan, A. Demers, S. Shenker and L. Zhang, MACAW: a Medium Access Control for Wireless LANs, ACM SIGCOMM Conference on Communications Architectures, Protocols, and Architectures, London, England, September 1994. This method adds an Acknowledgement (ACK) packet for acknowledging correct reception of the data packets, based on the MACA. Similarly, W. Diepstraten et al proposed a DFWMAC method, see W. Diepstraten, G Ennis and P. Belanger, Distributed Foundation Wireless Medium Access Protocol, IEEE, P802.11/93-190; and C. L. Fullmer et al proposed FAMA, see C. L. Fullmer and J. J. Garcia-Luna Aceves, Solutions to Hidden Terminal Problems in Wireless Networks, ACM SIGCOMM Conference on Communication Architectures, Protocols and Architectures, Cannes, France, September 1997. These methods all use a handshaking procedure of RTS-CTS-DATA-ACK based on the carrier sensing, and the problems of hidden terminals and exposed terminal are well solved by virtual channel preservations.
On the basis of the above schemes, the 802.11 standard defines a Distributed Coordination Function (DCF) for Contention Period (CP) which is based on the Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) protocol and each node independently decides to access the channel and when it fails, enters into a backoff procedure in order to re-access the channel. In addition, the DCF uses a handshaking procedure of DATA/ACK or RTS/CTS/DATA/ACK, and along with a Network Allocation Vector (NAV), provides a more flexible and effective wireless communication protocol in a self-organized manner.
Next, the distributed coordination function with a handshaking procedure of RTS/CTS will be described with reference to FIG. 1. In particular, as shown in FIG. 1, when one transmitting node in the wireless network has a packet arriving, if it senses that a channel is idle and an idle time period is more than or equal to a DCF Interframe Space (DIFS), then an RTS packet is immediately sent. On the contrary, if it senses that the channel is busy or the idle time period is less than DIFS, then a backoff procedure is performed until the channel is idle and the idle time period is equal to DIFS. After the backoff procedure, the RTS packet is sent. The RTS packet contains a Transmitter Address (TA), a Receiver Address (RA), and a Duration required for finishing subsequent packet transmission. Here, a value of the Duration indicates a time period during which the channel is to be occupied, and thus functions as the channel preservations. The value of the Duration equals to a sum of a duration required for sending the subsequent data packet (DATA), a time period for sending one CTS packet, a time period for sending one ACK packet, and a time period of three Short Interframe Spaces (SIFS). It should be noticed that the RTS/CTS is not necessary, but optional. The operator may decide whether the RTS/CTS is used or not, or in which cases the RTS/CTS is used, according to its particular implementations. Generally, one parameter is used to indicate a threshold of a packet length for which the RTS/CTS will be used, and when the data packet is equal or longer than that threshold, the RTS/CTS handshaking procedure is used. If the data packet is less than the threshold, the RTS/CTS handshaking procedure is then not necessary, and the data packet is directly sent.
After correctly receiving the RTS and waiting for one short interframe space, the receiving node responds with the CTS packet, the contents of which include the Receiver Address RA copied from the TA field of the received RTS and a duration required for finishing subsequent packet transmission. The duration is equal to the Duration value copied from the received RTS minus the time period for sending the CTS packet and a time period of one SIFS (i.e., the SIFS before the receiving node sends the CTS packet shown in FIG. 1). After successfully receiving the CTS sent back by the receiving node, the transmitting node waits for one SIFS, and then sends the DATA packet.
DCF utilizes a data packet transmission mechanism that supports fragmentation. When a data packet from an upper layer is long, for example, more than a data fragment threshold length defined in the MAC layer, this data packet will be divided. That is to say, when data is long, it will be divided into multiple fragments. At the header of the packet or the packet fragment, a field More Fragments of 1 bit is defined for indicating whether a fragment belonging to the data packet is not yet transmitted. For example, when a value of the field More Fragments is “1”, it may indicate that more fragments are not yet transmitted. In other cases, the value of the field More Fragments will be “0”. The field More Fragments is also contained in the data packet and the data packet fragment. When the receiving node receives one fragment, it checks whether the value of More Fragments is zero or not. If the value of More Fragments is not zero, then it means some fragments are not yet transmitted. In this case, the value of the Duration field of this data packet is equal to a sum of a time period for sending next data packet fragment, a time period for sending two ACKs, and a time period of three SIFSs (i.e., the duration field of Fragment 0 shown in FIG. 1 will indicate that the channel will be preserved until a time instant of the end of ACK1). The duration value of the ACK responded by the receiving node will not be zero, but equal to the value of the duration copied from the duration field of the received data packet fragment minus a time period for sending one ACK packets and a time period of one SIFS (i.e., the duration field of ACK 0 shown in FIG. 1 also indicates that the channel will be preserved until the time instant of the end of ACK1). When successfully receiving all fragments of the data packet, the receiving node waits for one SIFS, and then sends an acknowledgement (ACK) packet for confirmation. When the last fragment is sent, the last responded ACK has a duration of zero (i.e., the value of the duration of ACK3 shown in FIG. 1 is zero).
Simultaneously, for avoiding packet collisions among the hidden terminals, all the non-receiving nodes that successfully receive the RTS within the communication range of the transmitting node, and all the non-transmitting nodes that successfully receive the CTS within the communication range of the receiving node, after receiving the above packets, compare Duration values of these packets with the current NAV values of their own, and update the NAV values with a larger one. All the nodes negotiate that only when its NAV value is zero, a contention will be initiated in order to access a wireless channel.
Thus, by use of the handshaking procedures and the carrier sense based on backoff algorithm, the collision probability that each independent node accesses the channel is reduced in the distributed network; and by use of introducing NAV to virtually preserve the wireless resources, packet access of other nodes within the communication ranges of the current pair of the communication nodes is suppressed. To a certain extent, a collision-free transmission of the data packets of the current pair of the communication nodes is ensured.
Although the above prior arts may reduce the probability of the data packet collisions through carrier sense and short packet exchanges, compared with central coordinated MAC protocols, the performance of the distributed medium access control method is still limited by the packet collisions occurring in the course of the nodes' contentions of channels.